Due to the ever increasing demand for data storage in today's digital world, distributed storage systems have received a lot of attention. In the distributed storage system, data as a whole or different portions of the data is spread over several physically separate computer storage servers (also known as storage nodes). The total storage capacity of the distributed storage system is designed to be much greater than that of a single storage node—i.e., the sum of the storage of all individual storage nodes. With many physical servers in the highly distributed storage system, there is a relative increase in the possibility of failure—temporary or permanent as compared to a single storage node. If a node with some fraction of the data stored becomes unavailable for any reason, the distributed storage system provides the data from an alternative node (i.e., any other nodes part of the distributed storage system). In this manner, the required data is accessible by clients via the alternative node.
Clients accessing data prefer to know which storage nodes have copies so that multiple alternatives can be tried. As per known methods, there are two mechanisms that enable the clients to find out where the data is located—one is to ask a known authority node/central node, and second is to find out directly from the data reference/address. The former way is not fault-tolerant as the central node may fail, then all storage nodes become inaccessible. The second way is preferred in large horizontally scalable systems.
One way to find out the data reference is via a consistent hashing. Consistent hashing is a way to locate data amongst a number of distributed nodes in the storage system, where the client is enabled to know exactly which nodes to be contacted without any central authority. Many systems that use consistent hashing view the numeric data reference address as a number that describes a position on a circle, the circle includes a number of storage nodes in a pre-defined fashion. A reference typically ranges from 0 to a large integer (often 2^n for some n) and a node ID is labeled on multiple positions around the circle. To find the data, the client starts at the position pointed to by the data reference and moves clockwise around the circle of potential positions until a valid (non-null) node ID is found. The node which is found and the next N nodes (N being the known number of redundant copies of data) further around from this one in the same direction are the nodes that contain the required data.
The physical nodes/devices are given IDs on this numeric circle to ensure that redundant copies of the data, when placed on a contiguous number of nodes in the circular ordering, are in fact on physical devices that are unlikely to suffer a coincident or correlated failure. This is to minimize the chance that all N copies of the data will become unavailable if one (or a small number) of nodes fail.
In general all data placement schemes follow the basic method of first calculating the initial position of the data in the circular hashing space (i.e. locate the starting position on this circle of potential node IDs). Then, count incrementally around the circle from this position to find (for storing) the required IDs of nodes that store the data. For reading data, the first node that all is required.
Once the starting position is found, the series of nodes that store the redundant copies is identical in these schemes. This approach is vulnerable to the problem of cascading failure, where the failure of a node causes all the clients to pass their requests onto another next node which can result in increasing the load on the node sufficient to make it fail. This effect then continues to another next node in an amplified way, thus increasing the chances of a total system failure.
Some solutions randomize the order of nodes around the circle so the sequence is not always fixed as read in a clockwise fashion. However, even with such arrangements it is still the case that a single node failure causes uneven distribution of load to other nodes.
Since issues of data storage arise almost everywhere in the modern world, there is a need for better methods and systems.